#include<stdio.h>
int existHelper(char** board, int rsize, int csize, char* word, int x, int y, int ** walked) {   		 		 
    if (*word == '\0') {   		 		 
        return 1;
    }
    if (x > 0 && board[x-1][y] == *word && !walked[x-1][y]) {   		 		 
        walked[x-1][y] = 1;
        if (existHelper(board, rsize, csize, word+1, x-1, y, walked)) {   		 		 
            return 1;
        }
        walked[x-1][y] = 0;
    }
    if (y > 0 && board[x][y-1] == *word && !walked[x][y-1]) {   		 		 
        walked[x][y-1] = 1;
        if (existHelper(board, rsize, csize, word+1, x, y-1, walked)) {   		 		 
            return 1;
        }
        walked[x][y-1] = 0;
    }
    if (x < rsize - 1 && board[x+1][y] == *word && !walked[x+1][y]) {   		 		 
        walked[x+1][y] = 1;
        if (existHelper(board, rsize, csize, word+1, x+1, y, walked)) {   		 		 
            return 1;
        }
        walked[x+1][y] = 0;
    }
    if (y < csize - 1 && board[x][y+1] == *word && !walked[x][y+1]) {   		 		 
        walked[x][y+1] = 1;
        if (existHelper(board, rsize, csize, word+1, x, y+1, walked)) {   		 		 
            return 1;
        }
        walked[x][y+1] = 0;
    }
    return 0;
}   		 		 
int exist(char** board, int boardRowSize, int boardColSize, char* word) {   		 		 
    int** walked = malloc(sizeof(int*) * boardRowSize);
    int i, j;
    for (i = 0 ; i < boardRowSize ; i++) {   		 		 
        walked[i] = malloc(sizeof(int) * boardColSize);
        for (j = 0 ; j < boardColSize ; j++) {   		 		 
            walked[i][j] = 0;
        }
    }
    for (i = 0 ; i < boardRowSize ; i++) {   		 		 
        for (j = 0 ; j < boardColSize ; j++) {   		 		 
            if (board[i][j] == *word) {   		 		 
                walked[i][j] = 1;
                if (existHelper(board, boardRowSize, boardColSize, word+1, i, j, walked)) {   		 		 
                    return 1;
                }
                walked[i][j] = 0;
            }
        }
    }
    return 0;
}   		 		 
int main(int argc, char **argv)
{   		 		 
char ** array;
    printf("Please input the array width and height\n");
    int n,i,w,h;
    scanf("%d,%d",&w,&h);
    array = (char*)malloc(sizeof(char)*h);
    for(i=0; i < h; i++)
    {   		 		 
        array[i] =  malloc(sizeof(char) * w);
        printf("Please input the %d-th string\n",i);
        scanf("%s",array[i]);
    }
    printf("Please input the search word\n");
    char word[128];
    scanf("%s",word);
    int result= exist(array, h, w, word);
    if(result == 1)
    {   		 		 
        printf("searched\n");
    }else
    {   		 		 
        printf("unsearched\n");
    }
  


return 0;
}   		